import java.util.*;

public class 合并区间 {
    /**
     * https://leetcode.cn/problems/merge-intervals/?envType=problem-list-v2&envId=array
     * 堆 + 模拟
     */

    public int[][] merge(int[][] intervals) {
        //长度为1直接返回
        if(intervals.length == 1){
            return intervals;
        }
        //堆排序, 按照第一个元素的大小从小到大排序
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> x[0] - y[0]);
        for(int[] num : intervals){
            heap.add(num);
        }
        //用一个动态数组存储一下
        List<int[]> ret = new ArrayList<>();
        //弹出一个元素来进行比较
        int[] cur = heap.poll();
        while(!heap.isEmpty()){
            int[] next = heap.poll();
            //前一个元素的末尾大于等于下一个元素的头, 可以合并
            if(cur[1] >= next[0]){
                //防止1,4 2,3这种情况, 取最大值
                cur[1] = Math.max(cur[1],next[1]);
            }else{
                //没有重叠直接加入ret中, cur修改成next继续比较
                ret.add(cur);
                cur = next;
            }
        }
        //边界处理, 最后一个元素会没有加进去
        ret.add(cur);
        int[][] ans = new int[ret.size()][2];
        int cnt = 0;
        for(int[] num : ret){
            ans[cnt++] = num;
        }
        return ans;
    }
}
